package com.squirrel.michale.search4;


/**
 * @author guanhao 观浩
 * @version 1.0.0.0
 * @createTime 2023/1/18 12:15 PM
 * @company Michale Squirrel
 * @link
 * @description
 */

/**
 * 给定一个非负整数 c ，你要判断是否存在两个整数 a 和 b，使得 a2 + b2 = c 。
 *
 *
 *
 * 示例 1：
 *
 * 输入：c = 5
 * 输出：true
 * 解释：1 * 1 + 2 * 2 = 5
 * 示例 2：
 *
 * 输入：c = 3
 * 输出：false
 *
 *
 * 提示：
 *
 * 0 <= c <= 231 - 1
 */
public class LeetCode0633 {

    public boolean judgeSquareSum(int c) {

        int left = 0;
        int right = (int) Math.sqrt(c);
        System.out.println("right=="+right);

        while (left <= right) {
            int diff = left*left - c + right*right;


            if (diff == 0) {
                System.out.println("left==" + left + "right==" + right + "c==" + c );
                return true;
            }else if (diff < 0){
                left++;
            }else{
                right--;
            }
        }
        return false;
    }


    /**
     * 5失败，如何解决
     *
     * @param c
     * @return
     */
    public boolean judgeSquareSum2(int c) {

        int left = 0;
        int right = c/2;

        long middle = 0;
        while (left <= right) {
            middle = left + ((right-left)>>1);
            long diff = middle*middle - c + left*left;

            if (diff == 0) {
                System.out.println("left==" + left + "middle==" + middle + "c==" + c );
                return true;
            }else if (diff < 0){
                left++;
            }else{
                right--;
            }
        }
        return false;
    }

    public static void main(String[] args) {

        LeetCode0633 leetCode633 = new LeetCode0633();
//        System.out.println(leetCode633.judgeSquareSum(5));
//        System.out.println(leetCode633.judgeSquareSum(2147483600));

//        2147483600
//        2147395600

        System.out.println(leetCode633.judgeSquareSum2(5));
//        System.out.println(leetCode633.judgeSquareSum2(2147483600));


    }

}
